def hanoi (n, src, dst, mid):
    global count
    count=0
    if n==1:
        print("{}:{}->{}".format(1,src,dst))
        count+=1
    else:
        hanoi(n-1,src,dst,mid)
        print("{}: {}->{}".format(n, src, dst))
        #把中间的移到最右侧
        hanoi(n-1,mid,dst,src)

hanoi(3,"A","B","C")
print(count)
